Random numbers, as results or outputs of random sources in random generators, are required for many applications. Random generators are methods that supply a sequence of random numbers. A critical criterion for the quality of random numbers is whether the result of the generating process can be regarded as independent of previous results.
Random numbers are required, for example, for cryptographic methods, being used to generate keys for these encoding methods. For example, random number generators (RNGs) are used to generate master keys for symmetrical encoding methods and protocol handshaking in elliptical curve cryptography (ECC), which prevent a power analysis attack and replay attacks.
There are two basic types of random generators, firstly pseudo-random number generators (PRNGs) for high throughputs and low security levels. In a PRNG usually a secret value is inputted, and each input value will always produce the same output series. A good PRNG, however, will output a series of numbers that appears random and that will withstand most tests.
It is noteworthy that high standards in terms of random properties are applied to keys for cryptographic methods. Pseudo-random number generators (PRNGs), represented e.g. by a linear feedback shift register (LRFS), are therefore not suitable for this purpose. Only a generator of truly random numbers, referred to as a true random number generator (TRNG), meets the relevant requirements. This represents the other type of random generator. In this, natural noise processes are used in order to obtain an unpredictable result.
Noise generators that utilize the thermal noise of resistors or semiconductors, or the shot noise at potential barriers or at p-n transitions, are usual. A further possibility is to utilize the radioactive decay of isotopes.
While the “classic” methods used analog elements, for example resistors, as noise sources, in the recent past digital elements, for example inverters, have been used. These have the advantage of less complexity in terms of circuit layout, since they exist as standard elements. In addition, such circuits can also be used in user-programmable circuits such as FPGAs.
It is known, for example, to use ring oscillators that represent an electronic oscillator circuit. With these, an odd number of inverters is interconnected to form a ring, so that an oscillation having a natural frequency is produced. The natural frequency depends on the number of inverters in the ring, the properties of the inverters, the interconnection conditions (i.e. lead capacitances), operating voltage, and temperature. The noise of the inverters causes a random phase shift to be produced with respect to the ideal oscillator frequency, which is used as a random process for the TRNG. It is noteworthy that ring oscillators oscillate independently and do not require external components such as capacitors or coils.
The output of the ring oscillators can be compressed or subjected to post-processing in order to compress or bundle (i.e. increase) entropy and eliminate any bias.
A problem in this connection is that the ring oscillator must be sampled as close as possible to an expected ideal edge so that a random sampled value is obtained. The publication of Bock, H., Bucci, M., Luzzi, R.: An Offset-Compensated Oscillator-Based Random Bit Source for Security Applications, CHES 2005, indicates how it is possible, by controlled shifting of the sampling point in time, always to sample in the vicinity of an oscillator edge.
European Patent No. 1 686 458 discloses a method for generating random numbers with the aid of a ring oscillator, in which a first and a second signal are made available, the first signal being sampled in a manner triggered by the second signal. In the method described, a ring oscillator is repeatedly sampled, in which context only non-inverting delays, i.e. an even number of inverters as delay elements, are always used. The oscillator ring is always sampled, simultaneously or with a mutual delay, after an even number of inverters beginning from a starting point. Shifting of the sampling point in time can thereby be omitted; instead, the multiple sampled signals are evaluated.
The publication “Design of Testable Random Bit Generators” by Bucci, M. and Luzzi, R. (CHES 2005) presents a method with which an influence on the random source can be identified. Attacks can thereby be prevented. A direct distinction between random values and deterministic values is, however, not possible therewith. It is possible to evaluate the quality of the random source by counting the transitions.
A further possibility is provided by the use of multiple ring oscillators. This is presented, for example, in the publication Sunar, B. et al.: A Provable Secure True Random Number Generator with Built In Tolerance Attacks, IEEE Trans. on Computers, January 2007. Here sampled values of several ring oscillators are combined with one another and evaluated.
As already stated, in ring oscillators an odd number of inverters is interconnected to form a ring, thereby producing an oscillation having a natural frequency. The natural frequency depends on the number of inverters in the ring, the properties of the inverters, the interconnection conditions (i.e. lead capacitances), operating voltage, and temperature. The noise of the inverters produces a random phase shift with respect to the ideal oscillator frequency, which is utilized as a random process for the TRNG.
An advantageous implementation of a TRNG source using a ring oscillator sampled at multiple points is shown in FIG. 1. This circuit at the same time offers the advantage that a correlation with the system clock can be identified, and faults can be discovered, when particular implementation conditions are present with a uniform capacitive load at all nodes of the ring oscillator, and when the circuit elements used (e.g. flip-flops, inverters) are configured in terms of design so that they react as homogeneously as possible to leading and trailing edges.
The publication “Design of Testable Random Bit Generators” by Bucci, M. and Luzzi, R. (CHES 2005) presents a method with which an influence on the random source can be identified. Attacks can thereby be prevented. A direct distinction between random values and deterministic values is, however, not possible therewith.
German Patent No. 60 2004 011 081 describes a possibility for testing a TRNG source after “post-processing,” as well as the manner in which this post-processing is shifted into a certification mode.